/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package com.google.code.peersim.pastry.protocol;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;

/**
 * Implementation of the Pastry <i>leaf-set</i>. A Pastry leafset stores {@code L}
 * {@link PastryId}s referring to nodes numerically close to the leaf-set owner.
 * More precisely {@code L/2} entries are those numerically closest larger ids,
 * and {@code L/2} entries are those numerically closest smaller ids.<br>
 * Typical values for {@code L} are {@code 2^b} or {@code 2*2^b}, where {@code b}
 * is given by {@link PastryProtocol#getB()} as defined in {@link PastryProtocol}.
 *
 * @see PastryProtocol
 * @author frusso
 * @version 0.1
 * @since 0.1
 */
class PastryLeafSet implements Iterable<PastryId> {

  /**
   * {@code L/2} entries are those numerically closest larger ids.
   */
  private final NavigableSet<PastryId> biggestOnes;
  /**
   * {@code L/2} entries are those numerically closest smaller ids.
   */
  private final NavigableSet<PastryId> smallestOnes;
  /**
   * Pastry's configuration parameter {@code L}.
   */
  private final int l;
  /**
   * Each half-set maximum size, equal to {@code L/2}.
   */
  private final int maxSize;
  /**
   * {@link PastryId} of the node owner of this leafset.
   */
  private final PastryId center;

  /**
   * Constructor.
   * 
   * @param l Pastry's {@code L} configuration parameter.
   */
  public PastryLeafSet(int l, PastryId center) {
    this.l = l;
    maxSize = l/2;
    biggestOnes = new TreeSet<PastryId>();
    smallestOnes = new TreeSet<PastryId>();
    this.center = center;
  }

  /**
   * Adds a new leaf to the leaf-set only if not already in.
   * 
   * @param id The new leaf
   * @return {@link Boolean#TRUE} if the leaf has been added, {@link Boolean#FALSE} otherwise
   */
  final boolean addLeaf(PastryId id) {
    boolean res = false;
    if(id.isLessThan(center)) {
      res = addToSmallests(id);
    } else {
      if(id.isGreaterThan(center)) {
        res = addToBiggests(id);
      }
    }
    return res;
  }

  /**
   * Tells whether the given id is stored in the leaf-set or not.
   *
   * @param id The id
   * @return Whether it is stored or not
   */
  boolean contains(PastryId id) {
    return biggestOnes.contains(id) || smallestOnes.contains(id);
  }

  /**
   * Empties the current leaf-set bringing its size down to zero.
   */
  final void empty() {
    this.biggestOnes.clear();
    this.smallestOnes.clear();
  }

  /**
   * Tries to find a replacement for the provided {@code deadNode} on the given
   * {@code leafSet}, which is generally a leaf-set received from an external node.
   *
   * @param deadNodeId The node to be replaced
   * @param leafSet The leaf-set to use
   */
  void findReplacementFor(PastryId deadNodeId, PastryLeafSet leafSet) {
    BigInteger minDst = null;
    PastryId replacement = null;

    boolean smaller = deadNodeId.isLessThan(center);
    for(PastryId candidate : leafSet) {
      // half-down
      if(smaller && candidate.isLessThan(center)) {
        BigInteger d2 = candidate.absDistance(center);
        if(minDst==null) {
          minDst = d2;
          replacement = candidate;
        }
        else {
          if(d2.compareTo(minDst)<0) {
            minDst = d2;
            replacement = candidate;
          }
        }
      }
      // half-up
      if(!smaller && candidate.isGreaterThan(center)) {
        BigInteger d2 = candidate.absDistance(center);
        if(minDst==null) {
          minDst = d2;
          replacement = candidate;
        }
        else {
          if(d2.compareTo(minDst)<0) {
            minDst = d2;
            replacement = candidate;
          }
        }
      }
    }
    if(replacement!=null)
      this.addLeaf(replacement);
  }

  /**
   * Returns an unmodifiable view of all the nodes currently stored in the
   * leaf-set.
   *
   * @return The unmodifiable view of all the nodes currently stored in the
   * leaf-set
   */
  final List<PastryNode> getAllLeaves() {
    List<PastryNode> list = new ArrayList<PastryNode>();
    for(PastryId id : this) {
      list.add(id.getNode());
    }
    return Collections.unmodifiableList(list);
  }

  /**
   * Returns the numerically closest {@link PastryId} to the provided input value,
   * or {@code null} the leaf-set is empty.
   *
   * @param key
   * @return
   */
  final PastryId getClosestId(PastryId key) {
    PastryId res = null;
    BigInteger min = null;
    for(PastryId id : this) {
      BigInteger dist = key.absDistance(id);
      if(min==null) {
        min = dist;
        res = id;
      } else {
        if(dist.compareTo(min)<0) {
          min = dist;
          res = id;
        }
      }
    }
    return res;
  }

  /**
   * Returns the numerically closest {@link PastryId} to the provided input value,
   * including the center of the leaf-set amongst the candidates. If the leaf-set
   * is empty, the center is returned. 
   *
   * @param key
   * @return
   */
  final PastryId getClosestIdCenterIncluded(PastryId key) {
    PastryId res = getClosestId(key);
    if(res!=null) {
      BigInteger distanceFromCenter = center.absDistance(key);
      if(distanceFromCenter.compareTo(res.absDistance(key))<0) {
        res = center;
      }
    } else {
      res = center;
    }
    return res;
  }

  /**
   * Returns the largest id in the half of ids in which the given {@code candidate}
   * falls. Returns {@code null} in case no such value can be found.
   *
   * @param candidate The candidate
   * @return The largest value or {@code null}
   */
  PastryId getLargestIndexFor(PastryId candidate) {
    if(candidate.isLessThan(center) && !smallestOnes.isEmpty())
      return this.smallestOnes.first();
    else
      if(!biggestOnes.isEmpty())
        return this.biggestOnes.last();
      else
        return null;
  }

  /**
   * States whether the give object identifier is within the range of the leaf-set.
   * Note that a {@link Boolean#TRUE} result does not mean the leaf-set stores a
   * node with the provided {@code id}.
   *
   * @param id The Pastry id
   * @return {@link Boolean#TRUE} iff {@code id} is in [{@link PastryLeafSet#min()}..{@link PastryLeafSet#max()}]
   * {@link Boolean#FALSE} otherwise
   */
  final boolean isWithinRange(PastryId id) {
    boolean res = false;
    if( (biggestOnes.size()+smallestOnes.size())>=2 ) {
      PastryId min = min();
      PastryId max = max();
      res = id.isGreaterThanOrEquals(min) && id.isLessThanOrEquals(max);
    }
    return res;
  }

  /**
   * States whether the current leaf-set is empty or not.
   *
   * @return {@link Boolean#TRUE} iff the leaf-set is empty, {@link Boolean#FALSE} otherwise
   */
  final boolean isEmpty() {
    return this.biggestOnes.isEmpty() && this.smallestOnes.isEmpty();
  }

  /**
   * Iterates over the stored identifiers in increasing numerical order, according
   * to the ordering function provided by the {@link PastryId} class.
   *
   * @return An unmodifiable {@link Iterator} of the leaf-set
   */
  public final Iterator<PastryId> iterator() {
    final Iterator<PastryId> lowestIt = smallestOnes.iterator();
    final Iterator<PastryId> highestIt = biggestOnes.iterator();

    return new Iterator<PastryId>() {
      
      /**
       * {@inheritDoc}
       */
      public boolean hasNext() {
        return lowestIt.hasNext() || highestIt.hasNext();
      }

      /**
       * {@inheritDoc}
       */
      public PastryId next() {
        PastryId next = null;
        if(lowestIt.hasNext()) {
          next = lowestIt.next();
        }
        else {
          if(highestIt.hasNext()) {
            next = highestIt.next();
          }
        }
        return next;
      }

      /**
       * {@inheritDoc}
       */
      public void remove() {
        throw new IllegalStateException("Opertaion not permitted.");
      }
    };
  }

  /**
   * Peeks the highest value in the leaf-set.
   *
   * @return The highest value or {@code null} if there are no elements.
   */
  final PastryId max() {
    PastryId max = null;
    if(biggestOnes.size()!=0) {
      max = biggestOnes.last();
    } else {
      if(smallestOnes.size()!=0) {
        max = smallestOnes.last();
      } else {
        // there are no elements, let's return null
      }
    }
    return max;
  }

  /**
   * Updates the current {@link PastryLeafSet} instance using the information
   * stored in the provided instance named {@code that}. This means that if {@code this}
   * has not reached its limit yet it can be filled in with the numerically-closest 
   * entries taken from {@code that}. Otherwise, should {@code this} be already full,
   * some of its entries would be replaced with numerically-closer ones taken from {@code that}.
   * Should {@code that} be empty or {@code null}, this method would simply do nothing.
   *
   * @param that The data structure used to update the current one
   * @return The current updated data structure
   */
  final PastryLeafSet merge(PastryLeafSet that) {
    if(that!=null && !that.isEmpty()) {
      for(PastryId pid : that) {
        addLeaf(pid);
      }
    }
    return this;
  }

  /**
   * Peeks the lowest value in the leaf-set.
   *
   * @return The lowest value or {@code null} if there are no elements.
   */
  final PastryId min() {
    PastryId min = null;
    if(smallestOnes.size()!=0) {
      min = smallestOnes.first();
    } else {
      if(biggestOnes.size()!=0) {
        min = biggestOnes.first();
      } else {
        // there are no elements, let's return null
      }
    }
    return min;
  }

  /**
   * Removes the given {@code id} from the leaf-set
   *
   * @param The entry that must be removed
   */
  void remove(PastryId id) {
    smallestOnes.remove(id);
    biggestOnes.remove(id);
  }

  /**
   * Returns the number of currently stored  entries.
   *
   * @return The number of currently stored  entries
   */
  final int size() {
    return this.biggestOnes.size() + this.smallestOnes.size();
  }

  /**
   * {@inheritDoc}
   */
  @Override
  public final String toString() {
    StringBuilder ids = new StringBuilder();
    ids.append("Lowers:\n");
    for(PastryId id : smallestOnes) {
      ids.append(id).append("\n");
    }
    ids.append("Highers:\n");
    for(PastryId id : biggestOnes) {
      ids.append(id).append("\n");
    }
    return new StringBuilder("PROPERTIES [L/2 down size: ").append(smallestOnes.size())
      .append(", L/2 up size: ").append(biggestOnes.size()).append(", center: ").append(center)
      .append("]\n").append(ids).toString();
  }

  /**
   * Adds the given {@code id} to the "biggest" set. In order to keep the set
   * within its {@link PastryLeafSet#maxSize}, should this operation make the
   * set exceed that limit, the greatest value would be removed. The method returns
   * {@link Boolean#FALSE} if, for any reason, {@code id} cannot be added to the
   * set, {@link Boolean#TRUE} otherwise.
   *
   * @param id The id we would like to add to the leaf-set
   * @return {@link Boolean#FALSE} if, for any reason, {@code id} cannot be added to the
   * set, {@link Boolean#TRUE} otherwise
   */
  private boolean addToBiggests(PastryId id) {
    boolean res = false;
    res = biggestOnes.add(id);
    if(biggestOnes.size()>maxSize) {
      PastryId max = biggestOnes.last();
      if(!biggestOnes.remove(max)) throw new IllegalStateException("Biggers leaf-set has exceeded its size.");
      if(max.equals(id)) res = false;
    }
    return res;
  }

  /**
   * Adds the given {@code id} to the "smallests" set. In order to keep the set
   * within its {@link PastryLeafSet#maxSize}, should this operation make the
   * set exceed that limit, the lowest value would be removed. The method returns
   * {@link Boolean#FALSE} if, for any reason, {@code id} cannot be added to the
   * set, {@link Boolean#TRUE} otherwise.
   *
   * @param id The id we would like to add to the leaf-set
   * @return {@link Boolean#FALSE} if, for any reason, {@code id} cannot be added to the
   * set, {@link Boolean#TRUE} otherwise
   */
  private boolean addToSmallests(PastryId id) {
    boolean res = false;
    res = smallestOnes.add(id);
    if(smallestOnes.size()>maxSize) {
      PastryId min = smallestOnes.first();
      if(!smallestOnes.remove(min)) throw new IllegalStateException("Smallers leaf-set has exceeded its size.");
      if(min.equals(id)) res = false;
    }
    return res;
  }
}